using System.Collections.Generic;
using System.Diagnostics;

namespace System.DataStructures
{
	/// <summary>
	/// A PascalSet space optimized for having fewer elements over a large range of integers.
	/// </summary>
	[DebuggerDisplay("{ToString()}")]
	internal sealed class SparsePascalSet : SetBase<int>
	{
		internal const int MinimumReservedBlocks = 2;

		private const int BitsMinus1 = BitsPerBlock - 1; //using the identity: x % BITS == x & (BITS-1)
		private const int BitsPerBlock = 1 << Log2BlockSize;
		private const int GrowthFactor = 2;
		private const int Log2BlockSize = 6;

		private ulong[] _bitBlocks; //Array of bit-blocks
		private int _blocksInUse;
		private int _count;
		private int[] _offsets; //Sorted array of bit-block offsets

		private uint _version;

		/// <summary>
		/// Initializes a new instance of the <see cref="SparsePascalSet"/> class.
		/// </summary>
		public SparsePascalSet()
		{
			_offsets = new int[MinimumReservedBlocks];
			_bitBlocks = new ulong[MinimumReservedBlocks];
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="SparsePascalSet"/> class.
		/// </summary>
		/// <param name="initialValues">The initial values.</param>
		public SparsePascalSet(IEnumerable<int> initialValues)
			: this()
		{
			if (initialValues == null)
			{
				return;
			}
			foreach (int value in initialValues)
			{
				Add(value);
			}
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="SparsePascalSet"/> class.
		/// </summary>
		/// <param name="initialValues">The initial values.</param>
		public SparsePascalSet(params int[] initialValues)
			: this()
		{
			if (initialValues == null)
			{
				return;
			}
			foreach (int value in initialValues)
			{
				Add(value);
			}
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="SparsePascalSet"/> class.
		/// </summary>
		/// <param name="checkSize">if set to <c>true</c>, ensures the requested reserve 
		/// is at least as big as the minimum reserve.</param>
		/// <param name="reservedBlockCount">The reserved block count.</param>
		private SparsePascalSet(bool checkSize, int reservedBlockCount)
		{
			if ((checkSize) && (reservedBlockCount < MinimumReservedBlocks))
			{
				reservedBlockCount = MinimumReservedBlocks;
			}
			_offsets = new int[reservedBlockCount];
			_bitBlocks = new ulong[reservedBlockCount];
		}

		/// <summary>
		/// Gets the number of items stored in this set.
		/// </summary>
		/// <value>The count.</value>
		public override int Count
		{
			get { return _count; }
		}

		/// <summary>
		/// Gets the max stored value.
		/// </summary>
		/// <value>The max stored value.</value>
		public int MaxStoredValue
		{
			get
			{
				int index = _blocksInUse - 1;
				while ((index >= 0) && (_bitBlocks[index] == 0))
				{
					index--;
				}
				if (index >= 0)
				{
					int bitCounter = 0;
					ulong mask = _bitBlocks[index];
					//only take the top 63 bits as 0 is stores as a 1 in the least significant bit.
					while ((mask >>= 1) > 0)
					{
						bitCounter++;
					}
					return (_offsets[_blocksInUse - 1] << Log2BlockSize) + bitCounter;
				}
				return -1;
			}
		}

		/// <summary>
		/// Gets the count of storage blocks in use.
		/// </summary>
		/// <value>The blocks in use.</value>
		internal int BlocksInUse
		{
			get { return _blocksInUse; }
		}

		internal int BlocksReserved
		{
			get { return _bitBlocks.Length; }
		}

		/// <summary>
		/// Adds the specified value to the set.
		/// </summary>
		/// <param name="value">The value.</param>
		public override bool Add(int value)
		{
			Guard.GreaterThanOrEqualTo(0, value, "value");

			int offset = value >> Log2BlockSize;
			int offsetIndex = FindOffsetIndex(offset);
			if ((offsetIndex >= _blocksInUse) || (_offsets[offsetIndex] != offset))
			{
				InsertBlock(offsetIndex, offset);
			}
			ulong oldBitBlock = _bitBlocks[offsetIndex];
			ulong newBitBlock = oldBitBlock | (1UL << (value & BitsMinus1));
			if (oldBitBlock != newBitBlock)
			{
				_bitBlocks[offsetIndex] = newBitBlock;
				_count++;
				_version++;
				return true;
			}
			return false;
		}

		/// <summary>
		/// Removes all objects from the set.
		/// </summary>
		public override void Clear()
		{
			_blocksInUse = 0;
			_count = 0;
			_version++;
		}

		/// <summary>
		/// Clones the set, trimming reserved space if specified.
		/// </summary>
		/// <param name="trimReservedSpace">if set to <c>true</c> [trim reserved space].</param>
		/// <returns>A cloned instance.</returns>
		public SparsePascalSet Clone(bool trimReservedSpace = false)
		{
			SparsePascalSet newSet = new SparsePascalSet(!trimReservedSpace, _offsets.Length);
			Array.Copy(_offsets, newSet._offsets, _offsets.Length);
			Array.Copy(_bitBlocks, newSet._bitBlocks, _bitBlocks.Length);
			newSet._blocksInUse = _blocksInUse;
			newSet._count = _count;
			return newSet;
		}

		public override ISetEx<int> CloneType(IEnumerable<int> initialContents = null)
		{
			return new SparsePascalSet(initialContents);
		}

		/// <summary>
		/// Compacts this instance, leaving the specified reserved block count of available storage.
		/// </summary>
		/// <param name="reservedBlockCount">The reserved block count.</param>
		public void Compact(int reservedBlockCount = MinimumReservedBlocks)
		{
			List<int> usedBlocks = new List<int>();
			for (int i = 0; i < _blocksInUse; i++)
			{
				if (_bitBlocks[i] != 0)
				{
					usedBlocks.Add(i);
				}
			}

			int newSize = usedBlocks.Count + ((reservedBlockCount < MinimumReservedBlocks) ? MinimumReservedBlocks : reservedBlockCount);
			if (newSize == _offsets.Length)
			{
				return;
			}
			int[] newOffsets = new int[newSize];
			ulong[] newBitBlocks = new ulong[newSize];

			for (int i = 0; i < usedBlocks.Count; i++)
			{
				int j = usedBlocks[i];
				newOffsets[i] = _offsets[j];
				newBitBlocks[i] = _bitBlocks[j];
			}

			_offsets = newOffsets;
			_bitBlocks = newBitBlocks;
			_blocksInUse = usedBlocks.Count;
			_version++;
		}

		/// <summary>
		/// Returns <see langword="true"/> if this set contains the specified element.
		/// </summary>
		/// <param name="value">The object to locate in the <see cref="T:System.Collections.Generic.ICollection`1"/>.</param>
		/// <returns>
		/// 	<see langword="true"/> if this set contains the specified element, <see langword="false"/> otherwise.
		/// </returns>
		public override bool Contains(int value)
		{
			if (value < 0)
			{
				return false;
			}
			int offset = value >> Log2BlockSize;
			int offsetIndex = FindOffsetIndex(offset);
			if ((offsetIndex >= _blocksInUse) || (_offsets[offsetIndex] != offset))
			{
				return false;
			}
			return (0 != (_bitBlocks[offsetIndex] & (1UL << (value & BitsMinus1))));
		}

		public override ISetEx<int> Difference(IEnumerable<int> items)
		{
			SparsePascalSet result = Clone();
			if (!items.IsNullOrEmpty())
			{
				SparsePascalSet other = items as SparsePascalSet;
				if (other != null)
				{
					result.DifferenceWith(other);
				}
				else
				{
					result.DifferenceWith(items);
				}
			}
			return result;
		}

		public void DifferenceWith(SparsePascalSet set)
		{
			if (set.IsNullOrEmpty())
			{
				return;
			}
			BinaryMerge(set, (a, b) => a & (a ^ b));
		}

		public override void DifferenceWith(IEnumerable<int> items)
		{
			if (items.IsNullOrEmpty())
			{
				return;
			}
			SparsePascalSet other = items as SparsePascalSet;
			if (other != null)
			{
				DifferenceWith(other);
			}
			else
			{
				base.DifferenceWith(items);
			}
		}

		/// <summary>
		/// Determines whether the specified <see cref="T:System.Object"></see> is equal to the current <see cref="T:System.Object"></see>.
		/// </summary>
		/// <param name="obj">The <see cref="T:System.Object"></see> to compare with the current <see cref="T:System.Object"></see>.</param>
		/// <returns>
		/// true if the specified <see cref="T:System.Object"></see> is equal to the current <see cref="T:System.Object"></see>; otherwise, false.
		/// </returns>
		public override bool Equals(object obj)
		{
			if ((obj != null) && (obj is SparsePascalSet))
			{
				return Equals((SparsePascalSet)obj);
			}
			return false;
		}

		/// <summary>
		/// Determines whether the specified <see cref="SparsePascalSet"></see>s are equal.
		/// </summary>
		/// <param name="leftSet">The left set.</param>
		/// <param name="other">The right set.</param>
		/// <returns>True if both specified sets are equal, otherwise false.</returns>
		public bool Equals(SparsePascalSet other)
		{
			if (other == null)
			{
				return false;
			}

			int i = 0,
			    j = 0;
			while (i < _blocksInUse || j < other._blocksInUse)
			{
				if (i < _blocksInUse && (j >= other._blocksInUse || _offsets[i] < other._offsets[j]))
				{
					if (_bitBlocks[i++] != 0)
					{
						return false;
					}
				}
				else if (j < other._blocksInUse && (i >= _blocksInUse || _offsets[i] > other._offsets[j]))
				{
					if (other._bitBlocks[j++] != 0)
					{
						return false;
					}
				}
				else
				{
					// equal keys
					if (_bitBlocks[i++] != other._bitBlocks[j++])
					{
						return false;
					}
				}
			}
			return true;
		}

		/// <summary>
		/// Returns an enumerator that iterates through the collection.
		/// </summary>
		/// <returns>
		/// A <see cref="T:System.Collections.Generic.IEnumerator`1"></see> that can be used to iterate through the collection.
		/// </returns>
		/// <exception cref="Exception"><see cref="SparsePascalSet"/> was modified after the enumerator was instantiated.</exception>
		public override IEnumerator<int> GetEnumerator()
		{
			uint version = _version;

			int currentIndex = -1;
			int currentOffsetValue = 0;
			ulong currentBitBlock = 0;
			ulong currentMask = 0;
			int currentBitCounter = 0;

			for (int i = 0; i < _count; i++)
			{
				if (version != _version)
				{
					throw new Exception("SparsePascalSet was modified after the enumerator was instantiated.");
				}

				//get a block to process
				while ((currentBitBlock == 0) && (currentIndex < _blocksInUse))
				{
					currentIndex++;
					currentOffsetValue = _offsets[currentIndex] << 6;
					currentBitBlock = _bitBlocks[currentIndex];
					currentMask = 1UL;
					currentBitCounter = 0;
				}

				//process the block
				while ((currentBitBlock & currentMask) == 0)
				{
					currentMask <<= 1;
					currentBitCounter++;
				}

				currentBitBlock &= ~currentMask;
				yield return currentOffsetValue + currentBitCounter;
			}
		}

		/// <summary>
		/// Serves as a hash function for a particular type. <see cref="M:System.Object.GetHashCode"></see> is suitable for use in hashing algorithms and data structures like a hash table.
		/// </summary>
		/// <returns>
		/// A hash code for the current <see cref="T:System.Object"></see>.
		/// </returns>
		public override int GetHashCode()
		{
			return base.GetHashCode();
		}

		public override ISetEx<int> Intersect(IEnumerable<int> items)
		{
			if (items.IsNullOrEmpty())
			{
				return new SparsePascalSet();
			}
			SparsePascalSet result = Clone();
			SparsePascalSet other = items as SparsePascalSet;
			if (other != null)
			{
				result.IntersectWith(other);
			}
			else
			{
				result.IntersectWith(items);
			}
			return result;
		}

		public void IntersectWith(SparsePascalSet set)
		{
			if (set.IsNullOrEmpty())
			{
				Clear();
				return;
			}
			BinaryMerge(set, (a, b) => a & b);
		}

		public override void IntersectWith(IEnumerable<int> items)
		{
			if (items.IsNullOrEmpty())
			{
				Clear();
				return;
			}
			SparsePascalSet other = items as SparsePascalSet;
			if (other != null)
			{
				IntersectWith(other);
			}
			else
			{
				base.IntersectWith(items);
			}
		}

		/// <summary>
		/// Determines whether the current instance is a subset of the specified <see cref="ISet&lt;T&gt;"/>.
		/// </summary>
		/// <param name="set">The set.</param>
		/// <returns>
		/// 	<c>true</c> if [is subset of] [the specified set]; otherwise, <c>false</c>.
		/// </returns>
		public bool IsSubsetOf(SparsePascalSet set)
		{
			if (set.IsNullOrEmpty())
			{
				return IsEmpty;
			}

			int thisIndex = 0;
			int thatIndex = 0;

			while (thisIndex < _blocksInUse)
			{
				int nextThisOffset = (thisIndex < _blocksInUse) ? _offsets[thisIndex] : int.MaxValue;
				int nextThatOffset = (thatIndex < set._blocksInUse) ? set._offsets[thatIndex] : int.MaxValue;

				if (nextThisOffset < nextThatOffset)
				{
					return false;
				}
				if (nextThisOffset == nextThatOffset)
				{
					ulong thisBitBlock = _bitBlocks[thisIndex++];
					ulong thatBitBlock = set._bitBlocks[thatIndex++];
					ulong allMask = thisBitBlock | thatBitBlock;
					if (thatBitBlock != allMask)
					{
						return false;
					}
				}
				else
				{
					thatIndex++;
				}
			}

			return true;
		}

		public override bool IsSubsetOf(IEnumerable<int> items)
		{
			SparsePascalSet other = items as SparsePascalSet;
			return (other != null) ? IsSubsetOf(other) : base.IsSubsetOf(items);
		}

		/// <summary>
		/// Determines whether the current instance is a superset of the specified <see cref="ISet&lt;T&gt;"/>.
		/// </summary>
		/// <param name="set">The set.</param>
		/// <returns>
		/// 	<c>true</c> if [is superset of] [the specified set]; otherwise, <c>false</c>.
		/// </returns>
		public bool IsSupersetOf(SparsePascalSet set)
		{
			return set.IsNullOrEmpty() || set.IsSubsetOf(this);
		}

		public override bool IsSupersetOf(IEnumerable<int> items)
		{
			SparsePascalSet other = items as SparsePascalSet;
			return (other != null) ? IsSupersetOf(other) : base.IsSupersetOf(items);
		}

		/// <summary>
		/// Removes the specified value from the set if it was there.
		/// </summary>
		/// <param name="value">The value.</param>
		public override bool Remove(int value)
		{
			if (value < 0)
			{
				return false;
			}

			int offset = value >> Log2BlockSize;
			int offsetIndex = FindOffsetIndex(offset);
			if ((offsetIndex >= _blocksInUse) || (_offsets[offsetIndex] != offset))
			{
				return false; //don't insert a new block just to set a 0.
			}
			ulong oldBitBlock = _bitBlocks[offsetIndex];
			ulong newBitBlock = oldBitBlock & ~(1UL << (value & BitsMinus1));
			if (oldBitBlock != newBitBlock)
			{
				_bitBlocks[offsetIndex] = newBitBlock;
				_count--;
				_version++;
				return true;
			}
			return false;
		}

		public override bool SetEquals(IEnumerable<int> items)
		{
			SparsePascalSet set = items as SparsePascalSet;
			return (set != null) ? Equals(set) : base.SetEquals(items);
		}

		public override ISetEx<int> SymmetricDifference(IEnumerable<int> items)
		{
			SparsePascalSet result = Clone();
			if (!items.IsNullOrEmpty())
			{
				SparsePascalSet other = items as SparsePascalSet;
				if (other != null)
				{
					result.SymmetricDifferenceWith(other);
				}
				else
				{
					result.SymmetricDifferenceWith(items);
				}
			}
			return result;
		}

		public void SymmetricDifferenceWith(SparsePascalSet set)
		{
			if (set.IsNullOrEmpty())
			{
				return;
			}
			BinaryMerge(set, (a, b) => a ^ b);
		}

		public override void SymmetricDifferenceWith(IEnumerable<int> items)
		{
			if (items.IsNullOrEmpty())
			{
				return;
			}
			SparsePascalSet other = items as SparsePascalSet;
			if (other != null)
			{
				SymmetricDifferenceWith(other);
			}
			else
			{
				base.SymmetricDifferenceWith(items);
			}
		}

		/// <summary>
		/// Returns a <see cref="T:System.String"></see> that represents the current <see cref="T:System.Object"></see>.
		/// </summary>
		/// <returns>
		/// A <see cref="T:System.String"></see> that represents the current <see cref="T:System.Object"></see>.
		/// </returns>
		public override string ToString()
		{
			return string.Format("{{{0}}}", string.Join(", ", this));
		}

		public override ISetEx<int> Union(IEnumerable<int> items)
		{
			SparsePascalSet result = Clone();
			if (!items.IsNullOrEmpty())
			{
				SparsePascalSet other = items as SparsePascalSet;
				if (other != null)
				{
					result.UnionWith(other);
				}
				else
				{
					result.UnionWith(items);
				}
			}
			return result;
		}

		public void UnionWith(SparsePascalSet set)
		{
			if (set.IsNullOrEmpty())
			{
				return;
			}
			BinaryMerge(set, (a, b) => a | b);
		}

		public override void UnionWith(IEnumerable<int> items)
		{
			if (items.IsNullOrEmpty())
			{
				return;
			}
			SparsePascalSet other = items as SparsePascalSet;
			if (other != null)
			{
				UnionWith(other);
			}
			else
			{
				base.UnionWith(items);
			}
		}

		/// <summary>
		/// Gets the set after binary merge.
		/// </summary>
		/// <param name="other">The that.</param>
		/// <param name="merge">The binary operation.</param>
		/// <returns>A <see cref="SparsePascalSet"/></returns>
		private void BinaryMerge(SparsePascalSet other, Func<ulong, ulong, ulong> merge)
		{
			int totalBlocks = _blocksInUse + other._blocksInUse;
			int thisIndex = 0;
			int otherIndex = 0;

			while (thisIndex + otherIndex < totalBlocks)
			{
				int nextThisOffset = (thisIndex < _blocksInUse) ? _offsets[thisIndex] : int.MaxValue;
				int nextThatOffset = (otherIndex < other._blocksInUse) ? other._offsets[otherIndex] : int.MaxValue;
				int nextOffset = Math.Min(nextThisOffset, nextThatOffset);
				ulong mergedBits;

				if (nextOffset == nextThisOffset)
				{
					//in-place
					ulong originalBits = _bitBlocks[thisIndex];
					if (nextOffset == nextThatOffset)
					{
						//merge other
						mergedBits = merge(originalBits, other._bitBlocks[otherIndex]);
						_bitBlocks[thisIndex] = mergedBits;
						;
						thisIndex++;
						otherIndex++;
					}
					else
					{
						//merge nothing
						mergedBits = merge(originalBits, 0L);
						_bitBlocks[thisIndex] = mergedBits;
						thisIndex++;
					}
					_count = _count - BitCounter.CountBits(originalBits) + BitCounter.CountBits(mergedBits);
				}
				else
				{
					//insert other
					mergedBits = merge(0L, other._bitBlocks[otherIndex]);
					if (mergedBits > 0)
					{
						InsertBlock(thisIndex, nextOffset);
						_bitBlocks[thisIndex] = mergedBits;
						_count += BitCounter.CountBits(mergedBits);
						//increment to not overwrite
						thisIndex++;
						totalBlocks++;
					}
					//increment to consume
					otherIndex++;
				}
			}
		}

		/// <summary>
		/// Finds the index of the offset.
		/// </summary>
		/// <param name="offset">The offset.</param>
		/// <returns>An index of the offset in integer.</returns>
		private int FindOffsetIndex(int offset)
		{
			int left = 0,
			    right = _blocksInUse; // search interval is [left, right)
			while (left < right)
			{
				int index = (left + right)/2;
				if (offset == _offsets[index])
				{
					return index;
				}
				if (offset < _offsets[index])
				{
					right = index;
				}
				else
				{
					left = index + 1;
				}
			}
			return left; // index at which the offset *should* be, if it's not.
		}

		/// <summary>
		/// Inserts the block.
		/// </summary>
		/// <param name="offsetIndex">Index of the offset.</param>
		/// <param name="offset">The offset.</param>
		private void InsertBlock(int offsetIndex, int offset)
		{
			int lengthToMoveOut = _blocksInUse - offsetIndex;
			if (_bitBlocks.Length == _blocksInUse)
			{
				//Resize
				int newSize = _blocksInUse*GrowthFactor;
				int[] newOffsets = new int[newSize];
				ulong[] newBitBlocks = new ulong[newSize];
				Array.Copy(_offsets, newOffsets, offsetIndex);
				Array.Copy(_bitBlocks, newBitBlocks, offsetIndex);
				Array.Copy(_offsets, offsetIndex, newOffsets, offsetIndex + 1, lengthToMoveOut);
				Array.Copy(_bitBlocks, offsetIndex, newBitBlocks, offsetIndex + 1, lengthToMoveOut);
				_offsets = newOffsets;
				_bitBlocks = newBitBlocks;
			}
			else
			{
				//move out
				Array.Copy(_offsets, offsetIndex, _offsets, offsetIndex + 1, lengthToMoveOut);
				Array.Copy(_bitBlocks, offsetIndex, _bitBlocks, offsetIndex + 1, lengthToMoveOut);
			}
			//insert empty block
			_offsets[offsetIndex] = offset;
			_bitBlocks[offsetIndex] = 0; //clear all bits
			_blocksInUse++;
		}

		/// <summary>
		/// Gets the intersected set of the specified sets..
		/// </summary>
		/// <param name="set1">The set1.</param>
		/// <param name="set2">The set2.</param>
		/// <returns>The <see cref="SparsePascalSet"/>.</returns>
		public static SparsePascalSet operator &(SparsePascalSet set1, SparsePascalSet set2)
		{
			Guard.NotNull(set1, "set1");
			return (SparsePascalSet)set1.Intersect(set2);
		}

		/// <summary>
		/// Gets the union set of specified sets.
		/// </summary>
		/// <param name="set1">The set1.</param>
		/// <param name="set2">The set2.</param>
		/// <returns>The <see cref="SparsePascalSet"/>.</returns>
		public static SparsePascalSet operator |(SparsePascalSet set1, SparsePascalSet set2)
		{
			Guard.NotNull(set1, "set1");
			return (SparsePascalSet)set1.Union(set2);
		}

		/// <summary>
		/// Gets the set from exclusive or of the specified sets..
		/// </summary>
		/// <param name="set1">The set1.</param>
		/// <param name="set2">The set2.</param>
		/// <returns>The <see cref="SparsePascalSet"/>.</returns>
		public static SparsePascalSet operator ^(SparsePascalSet set1, SparsePascalSet set2)
		{
			Guard.NotNull(set1, "set1");
			return (SparsePascalSet)set1.SymmetricDifference(set2);
		}

		/// <summary>
		/// Gets the set from the difference of the specified sets.
		/// </summary>
		/// <param name="set1">The set1.</param>
		/// <param name="set2">The set2.</param>
		/// <returns>The <see cref="SparsePascalSet"/>.</returns>
		public static SparsePascalSet operator -(SparsePascalSet set1, SparsePascalSet set2)
		{
			Guard.NotNull(set1, "set1");
			return (SparsePascalSet)set1.Difference(set2);
		}
	}
}